package unit13_动态规划.part3_大厂冲刺题;

public class MinCut {
    public static void main(String[] args) {

    }

    public int minCut(String ss) {
        char[] s = ss.toCharArray();
        int n = s.length;
        if (n == 0) {
            return 0;
        }

        boolean[][] isPalin = new boolean[n][n];
        int[] f = new int[n + 1];
        int i, j, t;
        for (i = 0; i < n; i++) {
            for (j = i; j < n; j++) {
                isPalin[i][j] = false;
            }
        }
         //生成回文串
        for (t = 0; t < n; t++) {
            //奇数长度
            i = j = t;
            while (i >= 0 && j < n && s[i] == s[j]) {
                isPalin[i][j] = true;
                i--;
                j++;
            }
            //偶数长度

            i = t;
            j = t + 1;
            while (i >= 0 && j < n && s[i] == s[j]) {
                isPalin[i][j] = true;
                i--;
                j++;
            }

        }
        f[0] = 0;
        for (i = 1; i <= n; i++) {
            f[i] = Integer.MAX_VALUE;
            for (j = 0; j < i; j++) {
                if (isPalin[j][i - 1]) {
                    f[i] = Math.min(f[i], f[j] + 1);
                }
            }
        }
        return f[n] - 1;
    }
}
